The present invention relates to a distributor for improving the performance of a input-queueing Fast Packet Switch proposed to the switching structure of BISDN(Broadband Integrated Services Digital Network).
In general, the input-queueing fast packet switch has awoke a great interest because though the performance of the input-queueing fast packet switch is lower than that of an output-queueing fast packet switch which is another switching construction in the side of a maximum throughput and delay, the hardware construction of the former is simpler than that of the latter and the speed of a switching operation of the former is not higher than that of a input signal. However, the input-queueing fast packet switch shows a considerable drop in performance at a certain input traffic pattern because it does not efficiently make use of a Buffer, and the distributor is used for solving the above problem.
As the distributor is to generalize more than the function of the concentrator which is frequently used in a conventional circuit switching network, the distributor fulfills the function of concentrating and outputting the only active packet among input packets. The term "activity" in its original sense means that a packet slot is filled with a real packet. However, the definition of active could be extended depending on the application. It has been widely applied for a cost-effective implementation of switching systems or for separating active packets from the inactive packets. And then, the relation of positions between the active packets is preserved and the starting point of a concentrated active packet stream can become all output ports. Therefore, by being located the distributor before input buffers, the input active packets can be sequentially distributed to the buffers. That is, the difference of the number of the active packets which are stored in each buffer is one at most and consequently the buffer can be efficiently utilized.
Also, the distributor can consist of an internal-queueing fast packet switch, and the distributor is often used as the very important element consisting of a Multi-channel fast packet switch which preserves the sequence between the input packets.
The conventional distributor comprises a running adder and a reverse banyan network which is connected to the running adder. In the construction as stated above, the running adder computes a set of dummy header for the active input packets and plays a role of appending them at the head of the active packet. The appended dummy header is used for transferring the active packets to a final output port by the reverse-banyan network.
The dummy header appended by the running adder is removed after the active packets are transferred to the final output port, in the above conventional distributor, a complex hardware is required in order to fulfill the function of computing, appending and removing the dummy header. That makes the operation speed of the reverse banyan network to be higher than the transmition speed of the input packets.
The detailed construction and operation of the existing conventional distributor will be explained below(see FIG. 1).
FIG. 1A is a construction diagram of the conventional distributor and FIG. 1B an operation state diagram of a summing element. In the above drawings, 1 denotes the running adder, 2 represents a TOQ(Tail of queue) register and 3 the reverse banyan network.
The construction and a simplified operation of the conventional distributor as illustrated in drawings will be explained below.
The running adder 1 plays a role of computing dummy header for the active packet on the basis of the values stored in the TOQ register 2 and appends them to the packets. The value stored in the TOQ register 2 always indicates the buffer address which is ready to store the uppermost packet out of the input active packets arriving at the next time slot. Therefore, when all buffers are empty, the value of the TOQ register 2 becomes 0. As the input packets arrive, the value of the TOQ register 2 is updated through the running adder 1.
And the running adder 1 comprises a plurality of IP(Input Processor) 4, a plurality of summing elements 5 and a AG(Address Generator) 6. The input processor checks the activity bit field of the arrived packet on the input port i, and assigns the value 1 to its output line if it is active, and the value 0 otherwise.
The output value of the input processor 4 and the value stored in the TOQ register 2 are changed to the input values of the corresponding AG 6 out of a plurality of AGs 6 through a plurality of the summing elements 5.
The more detailed operation of the running adder is as follows.
First, the current value stored in the TOQ register 2 are added to the output value of the input processor IP0 through a modulo-N (the size of the distributor) operation. At the same time, the result values are directly transmitted to the address generator AG0, are added to the output value of the input processor IP1. This operation is continues to the last line of the running adder 1.
The final values of the summing element 5 are inputted to the address generator 6 and the respective address generators 6 subtract 1 from the final output value of the summing elements 5. The value becomes the dummy header of the corresponding active packet. And then because the input value of the lowest address generator always indicates the buffer address which should store the first active packets arriving at the next time slot, the value of the TOQ register 2 is renewed to the input value of the lowest address generator shown in FIG. 1A without any modification.
As shown in FIG. 1B, the summing element 5 receives the two input signals A, B, and outputs the signal B through one output port and the sum signal A+B mod N through the other output port. Here, the N indicates the number of the input signals for the input processor 4.
Consequently, as stated above, the conventional distributor as above mentioned has the problem that needs a complex hardware so as to fulfill the functions of computing, appending, and removing the dummy header.